//给你一个整数数组 nums。 
//
// nums 的子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列： 
//
// 
// (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x 
//- 1]) % 2 
// 
//
// 返回 nums 的 最长的有效子序列 的长度。 
//
// 一个 子序列 指的是从原数组中删除一些元素（也可以不删除任何元素），剩余元素保持原来顺序组成的新数组。 
//
// 
//
// 示例 1： 
//
// 
// 输入： nums = [1,2,3,4] 
// 
//
// 输出： 4 
//
// 解释： 
//
// 最长的有效子序列是 [1, 2, 3, 4]。 
//
// 示例 2： 
//
// 
// 输入： nums = [1,2,1,1,2,1,2] 
// 
//
// 输出： 6 
//
// 解释： 
//
// 最长的有效子序列是 [1, 2, 1, 2, 1, 2]。 
//
// 示例 3： 
//
// 
// 输入： nums = [1,3] 
// 
//
// 输出： 2 
//
// 解释： 
//
// 最长的有效子序列是 [1, 3]。 
//
// 
//
// 提示： 
//
// 
// 2 <= nums.length <= 2 * 10⁵ 
// 1 <= nums[i] <= 10⁷ 
// 
//
// Related Topics 数组 动态规划 👍 34 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-07-17 00:09:42
 * @description 3201.找出有效子序列的最大长度 I
 */
public class FindTheMaximumLengthOfValidSubsequenceI{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindTheMaximumLengthOfValidSubsequenceI fun=new FindTheMaximumLengthOfValidSubsequenceI();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //奇数位置 都是奇数/偶数 和偶数位置都是 奇数/偶数
	public int maximumLength1(int[] nums) {
		int[][] dp = new int[2][2];
		int res = 0;
		for (int num : nums) {
			num %= 2;
			for (int prev = 0; prev < 2; prev++) {
				// 如果当前数和前一个数模k相等，则可以构成有效子序列
				//找出所有满足nums[l] % k == nums[i] % k的l
				// 如果dp[prev][num] == 0，说明没有有效子序列

				//说白了，奇数和偶数位的元素模 k 同余
				//最终的子序列每个位上只有两种可能性
				//先确定num%k，再确定prev
				dp[prev][num] = dp[num][prev] + 1;
				// 更新最大长度
				// 01 11 21 +1
				// 02 12 22 +1
				// 01 11 21 +1
				res = Math.max(res, dp[prev][num]);
			}
		}
		return res;
	}

	//贪心整个数组，四种可能，全部是奇数 全部是偶数
	// 或者 奇数下标为奇数且偶数下标为偶数，以及奇数下标为偶数且偶数下标为奇数。
	public int maximumLength2(int[] nums) {
		int res = 0;
		// 分别对应四种情况
		int[][] patterns = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
		for (int[] pattern : patterns) {
			int cnt = 0;
			for (int num : nums) {
				if (num % 2 == pattern[cnt % 2]) {
					cnt++;
				}
			}
			res = Math.max(res, cnt);
		}
		return res;
	}

	/*
	*  只有三种情况，全奇数，全偶数，奇偶相间，奇偶相间不需要分成两种讨论，
	   第一个数是奇数就是奇数在前，偶数就是偶数在前。
       可以用一次循环操作三个计数器，奇数就奇数计数器加一，偶数同理
       如果当前数和上一个数奇偶不同则奇偶相间的计数器加一。
       然后可以用位运算优化掉if-else语句，
       思路是（一个数 & 1）可以取最低位，奇数最低位是1，偶数是0，
       奇数计数器加最低位，偶数计数器加（1 - 最低位），
       奇偶计数器加（当前最低位 异或 上一个数字的最低位）
	* */
	public int maximumLength(int[] nums) {
		int len_1 = 0;
		int len_2 = 0;
		int len_3 = 1;
		len_1 += 1 - (nums[0] & 1);
		len_2 += nums[0] & 1;
		for(int i = 1; i < nums.length; i++){
			len_1 += 1 - (nums[i] & 1); //偶数计数器
			len_2 += nums[i] & 1; //奇数计数器
			len_3 += (nums[i] & 1) ^ (nums[i - 1] & 1); // 奇偶交替计数器
		}
		return Math.max(len_1, Math.max(len_2, len_3));
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
